Tower of Hanoi Algorithm
The Tower of Hanoi Algorithm is a classic mathematical puzzle that was invented by the French mathematician Edouard Lucas in 1883. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: only one disk can be moved at a time, each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or an empty rod, and no disk may be placed on top of a smaller disk.
The Tower of Hanoi Algorithm is a recursive algorithm that provides an efficient solution to the puzzle, demonstrating the power of recursion in problem-solving. The algorithm involves breaking down the problem into smaller subproblems, solving them individually, and then combining the solutions to solve the original problem. The key idea of the algorithm is to move the top n-1 disks to an auxiliary rod, then move the largest disk to the target rod, and finally, move the n-1 disks from the auxiliary rod to the target rod. This process is repeated recursively for each subproblem until the base case is reached, where there is only one disk to be moved. The Tower of Hanoi Algorithm has a time complexity of O(2^n - 1), which means that the number of moves required to solve the puzzle doubles for each additional disk, making it an exponential growth problem.
#include <iostream>
using namespace std;
struct tower
{
int values[10];
int top;
} F, U, T;
void show()
{
cout << "\n\n\tF : ";
for (int i = 0; i < F.top; i++)
{
cout << F.values[i] << "\t";
}
cout << "\n\tU : ";
for (int i = 0; i < U.top; i++)
{
cout << U.values[i] << "\t";
}
cout << "\n\tT : ";
for (int i = 0; i < T.top; i++)
{
cout << T.values[i] << "\t";
}
}
void mov(tower &From, tower &To)
{
--From.top;
To.values[To.top] = From.values[From.top];
++To.top;
}
void TH(int n, tower &From, tower &Using, tower &To)
{
if (n == 1)
{
mov(From, To);
show();
}
else
{
TH(n - 1, From, To, Using);
mov(From, To);
show();
TH(n - 1, Using, From, To);
}
}
int main()
{
F.top = 0;
U.top = 0;
T.top = 0;
int no;
cout << "\nEnter number of discs : ";
cin >> no;
for (int i = no; i > 0; i--)
{
F.values[F.top++] = i;
};
show();
TH(no, F, U, T);
return 0;
}
